A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information.
In order to maintain an accurate representation of the network, routers periodically exchange routing information in accordance with a defined protocol. Large computer networks, such as the Internet, often include many routers grouped into administrative domains called “autonomous systems.” A single autonomous system may have one or more destination network prefixes, i.e., ranges of globally unique network addresses. The routing information exchanged between routers of different autonomous systems typically describes a set of network routes for reaching various destination network prefixes. In this manner, the routing information links topological information of the network with network prefixes, which can be used by the routers to forward packets.
When two routers initially connect, they typically exchange all of their routing information. The routers send control messages to incrementally update the routing information when the network topology changes. For example, the routers may send update messages to advertise newly available routes, and to withdraw routes that are no longer available.
Conventional routers often maintain the routing information in the form of one or more routing tables or other data structures. Due to the complexity of the Internet, the storage and maintenance of routing tables tends to consume significant router resources. Typical routing tables include an entry for each network route available for each destination prefix. Consequently, as the size and interconnectedness of the Internet has exploded over the last several years, so has the size of the routing tables.
In addition, a change in network topology can require significant resources and network bandwidth for the routers to exchange corrected routing information. A single change in network topology may affect tens of thousands, if not hundreds of thousands, of individual routes. The communication of update messages identifying new routes to reach destination prefixes, as well as withdraw messages to remove routes that are no longer available, can consume considerable computing resources and substantially delay rerouting of packets.